Consider the graph \(G = (V, E)\) with \(V = \{a, b, c\}\) and \(E = \{(a, b)\}\).

How many valid topological sorts of this graph are there?

Let \(G = (V,E)\) be the directed graph with \(V = \{a, b, c, d, e\}\) and \(E = \{(a, b), (a, c), (a, d), (b, e), (c, e), (d, e)\}\). How many valid topological sorts of $V$ are there?

Find a topological sort of the graph shown below:

d a b c e Show Answer

Suppose \(G\) is an acyclic directed graph. Let \(a\) and \(b\) be two nodes of \(G\) such that \(a\) appears before \(b\) in every possible topological sort of \(G\).

True or False: there must be a path from \(a\) to \(b\).